# -*- coding: utf-8 -*-            
# @Time : 2023/7/27 22:49
# @Author  : lining
# @FileName: n叉树的先序遍历.py
"""
不使用递归实现，用迭代实现，用栈实现，后进先出
（1）结果集放入根节点，把子节点放入中间节点
（2）从中间结果集取出最后一个数据，遍历子节点，子节点有子节点的就先把后面的数据放入中间结果，先去遍历子节点
"""


class Node():
    def __init__(self, value=0):
        """
        :param value:
        :param child: 列表形式，可存放多个子节点
        """
        self.value = value
        self.child = []


result = []
s = []


def Traversal(node):
    """
    :param node: 开始访问的节点
    :return:
    """
    if node is None:
        return
    result.append(node.value)
    if not node.child:
        return
    s.append(node.child)
    while s:
        current = s.pop()
        for a, b in enumerate(current):
            result.append(b.value)
            if b.child:
                s.append(current[a+1:])
                s.append(b.child)
                break
    print(result)


node = Node(1)
node1 = Node(2)
node2 = Node(3)
node3 = Node(4)
node4 = Node(5)
node5 = Node(6)
node6 = Node(7)
node7 = Node(8)
node8 = Node(9)
node9 = Node(10)
node10 = Node(11)
node11 = Node(12)
node12 = Node(13)
node.child.extend([node1,node2,node3,node4])
node2.child.extend([node5,node6,node7,node8])
node6.child.extend([node9,node10,node11,node12])
"""
                          (1)
              2        (3)        4       5
                6     (7)      8    9
                  10,11,12,13
"""
Traversal(node)


